#pragma once
#include <tuple>
#include <utility>
template<typename T>
struct deref{
  typedef T type;
};
template<typename T>
struct deref<T&> {
  typedef T type;
};
template<typename T>
struct deref<T&&> {
  typedef T type;
};
template<typename T>
using deref_t = typename deref<T>::type;
template<typename ...Ts>
auto dereference(std::tuple<Ts...> tpl){
  std::tuple<deref_t<Ts>...> ret = tpl;
  return ret;
}
template<int I, int N, int TO>
struct tuple_hash_ite {
  template<int NN>
  static void append_hashval(hashval_t *vals, hashval_t next) {
    vals[NN%3] += next;
    if (NN%3 == 2) {
      htab_mix(vals[0], vals[1], vals[2]);
    }
  }
  template<typename ...Ts>
  static hashval_t append(hashval_t *vals, const std::tuple<Ts...> &key) {
    if (sizeof(std::get<I>(key)) == 4) {
      append_hashval<N>(vals, *(hashval_t*)&std::get<I>(key));
      return tuple_hash_ite<I+1, N+1, TO>::append(vals, key);
    } else if (sizeof(std::get<I>(key)) == 8) {
      append_hashval<N>(vals, *(int*)&std::get<I>(key));
      append_hashval<N+1>(vals, *(int*)&std::get<I>(key));
      return tuple_hash_ite<I+1, N+2, TO>::append(vals, key);
    } else {
      assert(0);
    }
  }
};
template<int I, int N>
struct tuple_hash_ite<I, N, I> {
  template<typename ...Ts>
  static hashval_t append(hashval_t *vals, const std::tuple<Ts...> &key) {
      htab_mix(vals[0], vals[1], vals[2]);
      return vals[2];
  }
};

template<typename ...Ts>
struct tuple_key {
  typedef std::tuple<Ts...> key_type;
  static void copy(key_type &dst, const key_type &src) {
    dst = src;
  }

  static hashval_t hash(const key_type &key) {
    hashval_t vals[3] = {0x9e3779b9, 0x9e3779b9, 0};
    return tuple_hash_ite<0, 0, sizeof...(Ts)>::append(vals, key);
  }
  static hashval_t equal(const key_type &key1, const key_type &key2) {
    return key1 == key2;
  }
};
template<typename ...Ts>
tuple_key<deref_t<Ts>...> tuple_key_for_f(std::tuple<Ts...> tpl){
  return tuple_key<deref_t<Ts>...>{};
}
template<typename T>
using tie_key = decltype(tuple_key_for_f(std::declval<T>().tie()));
template<typename T>
using tuple_key_for = decltype(tuple_key_for_f(std::declval<T>()));